#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Seq_Queue Seq_Queue_t;
typedef struct Seq_Queue* pSeq_Queue_t;

struct Seq_Queue
{
    int *data;
    int size;
    int front;
    int rear;
};

//留一个处空间用来判断是否队满
//因此开辟的空间会比size多1
pSeq_Queue_t Init_Seq_Queue( int size )
{
    pSeq_Queue_t pseq_queue = ( pSeq_Queue_t )malloc( sizeof( Seq_Queue_t )  );
    if( NULL == pseq_queue )
    {
        printf( "malloc error" );
        return NULL;
    }
    //开辟一个size+1的数组
    pseq_queue->data = ( int * )malloc( sizeof( size + 1) );
    if( NULL == pseq_queue->data )
    {
        printf( "malloc error" );
        return NULL;
    }
    pseq_queue->front = 0;
    pseq_queue->rear = 0;
    pseq_queue->size = size + 1;

    return pseq_queue;
}

//判断是否表满
bool Is_Full_Seq_Queue(pSeq_Queue_t pseq_queue)
{
    if( (pseq_queue->rear + 1) % pseq_queue->size == pseq_queue->front )
        return true;
    else
        return false;
}

//判断是否表空
bool Is_Empty_Seq_Queue(pSeq_Queue_t pseq_queue)
{
    if( pseq_queue->front == pseq_queue->rear )
        return true;
    else
        return false;
}



//入列
void Push_Seq_Queue( pSeq_Queue_t pseq_queue , int data )
{
    //判断是否表满
    if( Is_Full_Seq_Queue( pseq_queue ) )
    {
        printf( "queue is full\n" );
        return;
    }
    //将元素入列
   pseq_queue->data[pseq_queue->rear] = data;
   //将rear指向的位置后移
   //因为算法是循环队列，所以需要对size取余
   //rear指向的节点是下一个元素要插入的空间
   //因此rear指向的不是真正的尾部
   pseq_queue->rear = ( pseq_queue->rear + 1 ) % pseq_queue->size;

}

//出列
int Pop_Seq_Queue( pSeq_Queue_t pseq_queue )
{
    //判断是否表空
    if( Is_Empty_Seq_Queue( pseq_queue ) )
    {
        printf( "queue is empty\n" );
        return false;
    }
    //将元素出列
    int data = pseq_queue->data[pseq_queue->front];
    //因为算法是循环队列，所以需要对size取余
    //front指向的是有效的数据空间，是真正的首节点数据
    pseq_queue->front = ( pseq_queue->front + 1 ) % pseq_queue->size;

    return data;
}

void Print_Seq_Queue( pSeq_Queue_t pseq_queue )
{
    if( Is_Empty_Seq_Queue( pseq_queue ) )
    {
        printf( "queue is empty\n" );
        return;
    }
    printf("队头-> ");
    int i = pseq_queue->front;
    while( i != pseq_queue->rear )
    {
        printf(" %d ",pseq_queue->data[i] );
        i = (i + 1) % pseq_queue->size;
    }
    printf("<-队尾");
    printf("\n");
    return ;
}

void Destory_Seq_Queue( pSeq_Queue_t pseq_queue )
{
    free( pseq_queue->data );
    free( pseq_queue );
    printf( "销毁成功\n" );
}


int main()
{
    pSeq_Queue_t pseq_queue = Init_Seq_Queue( 5 );
    if( NULL == pseq_queue )
    {
        printf( "Init_Seq_Queue error" );
        return -1;
    }
    Push_Seq_Queue( pseq_queue, 1 );
    Push_Seq_Queue( pseq_queue, 2 );
    Push_Seq_Queue( pseq_queue, 3 );
    Push_Seq_Queue( pseq_queue, 4 );
    Push_Seq_Queue( pseq_queue, 5 );
    Print_Seq_Queue( pseq_queue );
    Pop_Seq_Queue( pseq_queue );
    Pop_Seq_Queue( pseq_queue );
    Pop_Seq_Queue( pseq_queue );
    Print_Seq_Queue( pseq_queue );
    Push_Seq_Queue( pseq_queue, 6 );
    Push_Seq_Queue( pseq_queue, 7 );
    Print_Seq_Queue( pseq_queue );
    Destory_Seq_Queue( pseq_queue );



    return 0;
}